home *** CD-ROM | disk | FTP | other *** search
/ Aminet 12 / Aminet 12 (1996)(GTI - Schatztruhe)[!][Jun 1996].iso / Aminet / dev / e / framework.lha / fw / fastDictionary.e < prev    next >
Encoding:
Text File  |  1996-01-28  |  1.6 KB  |  64 lines
  1.  
  2. -> fastDictionary is a VERY efficient data structure for named objects.
  3. -> Time complexity for data adding is O(log n).
  4. -> Time complexity for data searching is also O(log n).
  5. -> Space complexity is O(n) + little extra penalty compared to dictionary.
  6.  
  7. -> Copyright © Guichard Damien 01/04/1996
  8.  
  9. OPT MODULE
  10. OPT EXPORT
  11.  
  12. MODULE 'fw/dictionary'
  13.  
  14. OBJECT fastDictionary OF dictionary
  15.   hashCode:INT
  16. ENDOBJECT
  17.  
  18. -> Creation method.
  19. -> MUST precede any call to a method, str MUST be non NULL.
  20. PROC create(str:PTR TO CHAR) OF fastDictionary
  21.   self.name:=str
  22.   self.hashCode:=self.hash(str)
  23. ENDPROC
  24.  
  25. -> Is object less than other.
  26. PROC isLessThan(other:PTR TO fastDictionary) OF fastDictionary
  27. ENDPROC self.hashCode<other.hashCode
  28.  
  29. -> Is object egal to other.
  30. PROC isEqualTo(other:PTR TO fastDictionary) OF fastDictionary
  31.   IF self.hashCode<>other.hashCode THEN RETURN FALSE
  32. ENDPROC StrCmp(other.name,self.name,ALL)
  33.  
  34. -> Is object greater than other.
  35. PROC isGreaterThan(other:PTR TO fastDictionary) OF fastDictionary
  36. ENDPROC self.hashCode>other.hashCode
  37.  
  38. -> Find an element in the tree.
  39. -> The first matching element is returned.
  40. -> Use continu() to find next occurrences.
  41. PROC find(key:PTR TO CHAR) OF fastDictionary
  42.   DEF hashValue:LONG
  43.   hashValue:=self.hash(key)
  44.   LOOP
  45.     IF self=NIL THEN RETURN NIL
  46.     IF hashValue<self.hashCode
  47.       self:=self.left
  48.     ELSEIF hashValue>self.hashCode
  49.       self:=self.right
  50.     ELSEIF StrCmp(key,self.name,ALL)
  51.       RETURN self
  52.     ELSE
  53.       self:=self.right
  54.     ENDIF
  55.   ENDLOOP
  56. ENDPROC
  57.  
  58. -> Hash function.
  59. PROC hash(key:PTR TO CHAR) OF fastDictionary
  60.   DEF hashValue=0:LONG
  61.   WHILE key[] DO hashValue:=hashValue+hashValue+key[]++
  62. ENDPROC hashValue
  63.  
  64.